{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Right Shifts to Sort the Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumRightShifts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组成为递增数组的最少右移次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>nums</code>&nbsp;，数组中的元素为&nbsp;<strong>互不相同</strong>&nbsp;的正整数。请你返回让 <code>nums</code>&nbsp;成为递增数组的 <strong>最少右移</strong>&nbsp;次数，如果无法得到递增数组，返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>一次 <strong>右移</strong>&nbsp;指的是同时对所有下标进行操作，将下标为 <code>i</code>&nbsp;的元素移动到下标&nbsp;<code>(i + 1) % n</code>&nbsp;处。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,4,5,1,2]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "第一次右移后，nums = [2,3,4,5,1] 。\n",
    "第二次右移后，nums = [1,2,3,4,5] 。\n",
    "现在 nums 是递增数组了，所以答案为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,3,5]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>nums 已经是递增数组了，所以答案为 0 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,4]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>无法将数组变为递增数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "\t<li><code>nums</code>&nbsp;中的整数互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-right-shifts-to-sort-the-array](https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-right-shifts-to-sort-the-array](https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,5,1,2]', '[1,3,5]', '[2,1,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        nums.append(nums[0])\n",
    "        cnt = 0\n",
    "        cur = -1\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                cnt += 1\n",
    "                cur = i\n",
    "        if cnt != 1:\n",
    "            return -1\n",
    "        return n - cur\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        i, n = 1, len(nums)\n",
    "        while i < n and nums[i - 1] < nums[i]: i += 1\n",
    "        if i == n: return 0\n",
    "        if nums[0] < nums[-1]: return -1\n",
    "        j = i\n",
    "        i += 1\n",
    "        while i < n and nums[i - 1] < nums[i]: i += 1\n",
    "        if i < n: return -1\n",
    "        return n - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sort_nums = sorted(nums)\n",
    "        if sort_nums ==  nums:\n",
    "            return 0\n",
    "        for i in range(1,n+1):\n",
    "            if nums[n-i:] + nums[:n-i] == sort_nums:\n",
    "                return i\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        nums.append(nums[0])\n",
    "        cnt = 0\n",
    "        cur = -1\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                cnt += 1\n",
    "                cur = i\n",
    "        if cnt != 1:\n",
    "            return -1\n",
    "        return n - cur\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        i, n = 1, len(nums)\n",
    "        while i < n and nums[i - 1] < nums[i]:\n",
    "            i += 1\n",
    "        if i == n:\n",
    "            return 0\n",
    "        if nums[0] < nums[-1]:\n",
    "            return -1\n",
    "        mid = i\n",
    "        i += 1\n",
    "        while i < n and nums[i - 1] < nums[i]:\n",
    "            i += 1\n",
    "        if i < n:\n",
    "            return -1\n",
    "        return n - mid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 1\n",
    "        while i < n and nums[i - 1] < nums[i]:\n",
    "            i += 1\n",
    "        if i == n:\n",
    "            return 0\n",
    "        if nums[0] < nums[-1]:\n",
    "            return -1\n",
    "        mid = i\n",
    "        i += 1\n",
    "        while i < n and nums[i - 1] < nums[i]:\n",
    "            i += 1\n",
    "        if i < n:\n",
    "            return -1\n",
    "        return n - mid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums == sorted(nums):\n",
    "                return ans\n",
    "            new = [nums[-1]] + nums[:-1]\n",
    "            nums = new\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if all(x < y for x, y in pairwise(nums)):\n",
    "                return i \n",
    "            nums = [nums[-1]] + nums[:-1]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        arr = sorted(nums)\n",
    "        count = 0\n",
    "        while arr != nums:\n",
    "            nums.insert(0, nums[-1])\n",
    "            nums = nums[:len(nums) - 1]\n",
    "            count += 1\n",
    "            if count > len(nums):\n",
    "                return -1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        def helper(arr):\n",
    "            for i in range(1, len(arr)):\n",
    "                if arr[i] <= arr[i-1]:\n",
    "                    return False\n",
    "            return True\n",
    "        n = len(nums)\n",
    "        if helper(nums):\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            res += 1\n",
    "            if helper(nums[i:]+nums[:i]):\n",
    "                return res\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        index = 0\n",
    "        num = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] < nums[i]:\n",
    "                index = i\n",
    "                num += 1\n",
    "        if num >= 2:\n",
    "            return -1\n",
    "        if num==0:\n",
    "            return 0\n",
    "        if nums[-1] > nums[0]:\n",
    "            return -1\n",
    "        return len(nums)-index-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        mid = -1\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                mid = i\n",
    "                break\n",
    "        else:\n",
    "            return 0\n",
    "        lst1 = nums[ : mid]\n",
    "        lst2 = nums[mid: ]\n",
    "        def pd(lst: list) -> bool:\n",
    "            tn = len(lst)\n",
    "            if tn == 1:\n",
    "                return True\n",
    "            for i in range(1, tn):\n",
    "                if lst[i] < lst[i - 1]:\n",
    "                    return False\n",
    "            return True\n",
    "        if pd(lst1) and pd(lst2) and min(lst1) > max(lst2):\n",
    "            return n - mid\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, A: List[int]) -> int:\n",
    "        for i in range(len(A)):\n",
    "            if all(x <= y for x, y in pairwise(A[-i:] + A[0:-i])): \n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\r\n",
    "        i, n = 1, len(nums)\r\n",
    "        while i < n and nums[i - 1] < nums[i]:\r\n",
    "            i += 1\r\n",
    "        if i == n:\r\n",
    "            return 0\r\n",
    "        if nums[0] < nums[-1]:\r\n",
    "            return -1\r\n",
    "        mid = i\r\n",
    "        i += 1\r\n",
    "        while i < n and nums[i - 1] < nums[i]:\r\n",
    "            i += 1\r\n",
    "        if i < n:\r\n",
    "            return -1\r\n",
    "        return n - mid\r\n",
    "\r\n",
    "    # 暴力\r\n",
    "    def minimumRightShifts2(self, nums: List[int]) -> int:\r\n",
    "        for i in range(len(nums)):\r\n",
    "            if all(x < y for x, y in pairwise(nums)):\r\n",
    "                return i\r\n",
    "            nums = [nums[-1]] + nums[:-1]\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        flag = False\n",
    "        for i in range(1, len(nums), 1):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                ans = len(nums)-i\n",
    "                flag = True\n",
    "                break\n",
    "        if flag == False:\n",
    "            return 0\n",
    "        else:\n",
    "            arr = nums[i:]+nums[:i]\n",
    "        for i in range(1, len(arr), 1):\n",
    "            if arr[i]<arr[i-1]:\n",
    "                return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        f = 0\n",
    "        while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "            f = 1\n",
    "            i += 1\n",
    "            \n",
    "        j = i + 1\n",
    "        cmp= nums[j - 1]\n",
    "\n",
    "        if i + 1 == n:\n",
    "            return 0\n",
    "        else:\n",
    "            i += 1\n",
    "            while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "                i += 1\n",
    "         \n",
    "            if nums[i] > cmp or (f and nums[i] > nums[0]):\n",
    "                return -1  \n",
    "            if i < n - 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return n - j\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if all(x < y for x, y in pairwise(nums)):\n",
    "                return i\n",
    "            nums = [nums[-1]] + nums[:-1]\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        flag = False\n",
    "        for i in range(n):\n",
    "            if nums[i] < nums[(i+1)%n]: continue\n",
    "            if flag: return -1\n",
    "            flag = True\n",
    "            res = n-1-i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "\n",
    "        #     if all(x < y for x, y in pairwise(nums)):\n",
    "        #         return i\n",
    "            \n",
    "        #     nums = [nums[-1]] + nums[:-1]\n",
    "        \n",
    "        # return -1\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        i = 0\n",
    "        while i <= n - 1:\n",
    "            if i == n - 1:\n",
    "                return 0\n",
    "            if (nums[i] > nums[i + 1]):\n",
    "                i += 1\n",
    "                break\n",
    "            i += 1\n",
    "\n",
    "        if all(x < y for x, y in pairwise(nums[i:])) and nums[-1] < nums[0]:\n",
    "            return n - i \n",
    "        \n",
    "        return -1\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 1\n",
    "        t = True\n",
    "        idx = 0\n",
    "        while i < n:\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                if t:\n",
    "                    t = False\n",
    "                    idx = i\n",
    "                else:\n",
    "                    return -1\n",
    "            i += 1\n",
    "        if not t and nums[-1] > nums[0]:\n",
    "            return -1\n",
    "        l = n - idx\n",
    "        if t:\n",
    "            return 0\n",
    "        else:\n",
    "            return l\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                    \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if nums == sorted(nums): return 0\n",
    "        for i in range(1, n+1):\n",
    "            if [nums[-1]] + nums[:-1] == sorted(nums):\n",
    "                return i\n",
    "            nums = [nums[-1]] + nums[:-1]\n",
    "        return -1\n",
    "        # # idx = -1\n",
    "        # # for i in range(n-1):\n",
    "        # #     if nums[i] > nums[i+1]:\n",
    "        # #         idx = i\n",
    "        # #         break \n",
    "        \n",
    "        # print(ans)\n",
    "        # print(idx)\n",
    "        # for i in range(idx+1, n):\n",
    "        #     if nums[i] > nums[idx]:\n",
    "        #         return -1\n",
    "        # return n - idx - 1 if idx != -1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        i = 1\n",
    "        n = len(nums)\n",
    "        while i < n and nums[i-1] <= nums[i]:\n",
    "            i += 1\n",
    "        if i == n:#只有一段\n",
    "            return 0\n",
    "        if nums[0] < nums[-1]: #至少两段 \n",
    "            return -1\n",
    "        mid = i\n",
    "        i += 1\n",
    "        while i < n and nums[i-1] <= nums[i]:\n",
    "            i += 1\n",
    "        if i < n:\n",
    "            return -1\n",
    "        return n-mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                key=i\n",
    "                cnt+=1\n",
    "        if cnt>1:\n",
    "            return -1\n",
    "        elif cnt==0:\n",
    "            return 0\n",
    "        else:\n",
    "            if nums[0]<nums[-1]:\n",
    "                return -1\n",
    "            return len(nums)-key\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        sort_nums=sorted(nums)\n",
    "        res,n= nums*2,len(nums)\n",
    "        if sort_nums==nums:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            if res[i:i+n]==sort_nums:\n",
    "                return n-i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sorted_nums = sorted(nums)\n",
    "        for i in range(n):\n",
    "            if nums[n-i:] + nums[:n-i] == sorted_nums:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i+1] < nums[i]:\n",
    "                break\n",
    "        else:\n",
    "            return 0\n",
    "        if nums[-1] > nums[0]:\n",
    "            return -1\n",
    "        flag=0\n",
    "        pos=0\n",
    "        for i in range(n-1):\n",
    "            if nums[i+1] < nums[i]:\n",
    "                flag+=1\n",
    "                if flag > 1:\n",
    "                    return -1\n",
    "                pos=n-(i+1)\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self,nums: List[int]) -> int:\n",
    "        i,n = 1,len(nums)\n",
    "        while i < n and nums[i-1] < nums[i]:\n",
    "            i += 1\n",
    "        if i == n:\n",
    "            return 0\n",
    "        if nums[0] < nums[-1]:\n",
    "            return -1\n",
    "        mid = i\n",
    "        i += 1\n",
    "        while i < n and nums[i-1] < nums[i]:\n",
    "            i += 1\n",
    "        if i < n:\n",
    "            return -1\n",
    "        return n - mid\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/solutions/2445703/cong-on2-dao-onzhi-duo-liang-duan-di-zen-yruq/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        arr = sorted(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            if v == arr[0]:\n",
    "                if nums[i:] + nums[:i] == arr:\n",
    "                    return (len(nums)-i)%len(nums)\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 1\n",
    "        while i < n and nums[i-1] < nums[i]:\n",
    "            i +=1\n",
    "        if i == n:\n",
    "            return 0\n",
    "\n",
    "        if(nums[0] < nums[-1]):\n",
    "            return -1\n",
    "        mid = i\n",
    "        i += 1\n",
    "        while i < n and nums[i-1] < nums[i]:\n",
    "            i += 1\n",
    "        if i < n:\n",
    "            return -1\n",
    "        return n - mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sorted_nums = sorted(nums)\n",
    "        for i in range(n):\n",
    "            if nums[n-i:] + nums[:n-i] == sorted_nums:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if all(x < y for x, y in pairwise(nums)):\n",
    "                return i\n",
    "            nums = [nums[-1]] + nums[:-1]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "\n",
    "            if all(x < y for x, y in pairwise(nums)):\n",
    "                return i\n",
    "            \n",
    "            nums = [nums[-1]] + nums[:-1]\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        mi=0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<nums[mi]:\n",
    "                mi=i\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[(mi+i)%len(nums)]>=nums[(mi+i+1)%len(nums)]:\n",
    "                return -1\n",
    "        return (len(nums)-mi)%len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sortedNums = sorted(nums)\n",
    "    \n",
    "        for i in range(n):\n",
    "            if nums == sortedNums:\n",
    "                return i\n",
    "            nums = [nums[-1]] + nums[:-1]  # 逆时针旋转数组\n",
    "    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        idx = []\n",
    "        for i in range(n):\n",
    "           if nums[i] -nums[(i-1)%n] <0:\n",
    "               idx.append(i)\n",
    "        if len(idx)>1:\n",
    "            return -1\n",
    "        elif idx[0] == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return n-idx[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        index = 0\n",
    "        num = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] < nums[i]:\n",
    "                index = i\n",
    "                num += 1\n",
    "        if num >= 2:\n",
    "            return -1\n",
    "        if num==0:\n",
    "            return 0\n",
    "        if nums[-1] > nums[0]:\n",
    "            return -1\n",
    "        return len(nums)-index-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        t=sorted(nums)\n",
    "        if t==nums:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            nums=[nums[-1]]+nums[:-1]\n",
    "            if nums==t:\n",
    "                return i+1\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = copy.deepcopy(nums)\n",
    "        ans.sort()\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if nums[i + 1] < nums[i]:\n",
    "                return - 1 if nums[i + 1:] + nums[:i + 1] != ans else n - i - 1 \n",
    "        return 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        start=-1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                if start<0:\n",
    "                    start=i \n",
    "                else:\n",
    "                    return -1\n",
    "        # return min(i+1,n-i)\n",
    "        if start<0:return 0\n",
    "        if nums[-1]<nums[0] and start>=0:\n",
    "            return n-start\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "\n",
    "        while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "            i += 1\n",
    "            \n",
    "        j = i + 1\n",
    "\n",
    "        if i + 1 == n:\n",
    "            return 0\n",
    "        else:\n",
    "            i += 1\n",
    "            while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "                i += 1\n",
    "         \n",
    "            if nums[i] > nums[j - 1] or (i and nums[i] > nums[0]):\n",
    "                return -1  \n",
    "            if i < n - 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return n - j\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "\n",
    "        while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "            i += 1\n",
    "            \n",
    "        j = i + 1\n",
    "\n",
    "        if i + 1 == n:\n",
    "            return 0\n",
    "        else:\n",
    "            i += 1\n",
    "            while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "                i += 1\n",
    "         \n",
    "            if nums[i] > nums[j - 1] or (i and nums[i] > nums[0]):\n",
    "                return -1  \n",
    "            if i < n - 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return n - j\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        def isAsc(arr):\n",
    "            return all(a<b for a,b in pairwise(nums))\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for _ in range(n):\n",
    "            if not isAsc(nums):\n",
    "                nums=[nums[-1]]+nums[:-1]\n",
    "                ans+=1\n",
    "        return ans if ans<n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if all(x < y for x, y in pairwise(nums)): # 递增判断\n",
    "                return i \n",
    "            nums = [nums[-1]] + nums[:-1] # 右移， 数组拼接\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        i, n = 1, len(nums)\n",
    "        while i < n and nums[i - 1] < nums[i]:\n",
    "            i += 1\n",
    "        if i == n:\n",
    "            return 0\n",
    "        if nums[0] < nums[-1]:\n",
    "            return -1\n",
    "        mid = i\n",
    "        i += 1\n",
    "        while i < n and nums[i - 1] < nums[i]:\n",
    "            i += 1\n",
    "        if i < n:\n",
    "            return -1\n",
    "        return n - mid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        # 主题是分成两个递增的数组，这样就可以进行右移，假如不能分成两个递增的数组，这样就不可以进行右移\n",
    "        # 通过几次整体右移能够形成递增数组，求最少的右移次数\n",
    "\n",
    "        i, n = 1, len(nums)\n",
    "\n",
    "        while i < n and nums[i - 1] < nums[i]:            # 这是找到第一段的递增数组\n",
    "            i += 1\n",
    "        if i == n:             # 这是原本就是递增数组\n",
    "            return 0\n",
    "\n",
    "        if nums[0] < nums[-1]:     # 这是不能组成递增数组的情况\n",
    "            return -1\n",
    "\n",
    "\n",
    "        mid = i\n",
    "        i += 1\n",
    "        while i < n and nums[i - 1] < nums[i]:\n",
    "            i += 1\n",
    "        if i < n:\n",
    "            return -1\n",
    "        return n - mid\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        minnum = 101\n",
    "        numlen = len(nums)\n",
    "        minidx = 0\n",
    "        for idx, item in enumerate(nums):\n",
    "            if item < minnum:\n",
    "                minnum = item\n",
    "                minidx = idx\n",
    "        print(minnum, minidx)\n",
    "        jdx = (minidx + 1 )% numlen\n",
    "        while jdx != minidx:\n",
    "            if nums[jdx%numlen] <= nums[(jdx+numlen-1)%numlen]:\n",
    "                # print(nums[jdx%numlen], nums[(jdx+numlen-1)%numlen])\n",
    "                return -1\n",
    "            else:\n",
    "                jdx = (jdx + numlen + 1) % numlen\n",
    "        return (numlen - minidx) % numlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        标记 = 1 if nums[-1] > nums[0] else 0\n",
    "        n = len(nums)\n",
    "        错位下标 = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                错位下标 = i\n",
    "                标记 += 1\n",
    "                if 标记 == 2:\n",
    "                    return -1\n",
    "        return n-错位下标 if 错位下标 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        prev = 0\n",
    "        first = 0\n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]\n",
    "            if num < prev:\n",
    "                if first > 0:\n",
    "                    return -1\n",
    "                first = i\n",
    "                prev = 0\n",
    "            else:\n",
    "                prev = num\n",
    "        if first == 0:\n",
    "            return 0\n",
    "        if nums[0] < nums[-1]:\n",
    "            return -1\n",
    "        return len(nums) - first\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        if nums==sorted(nums):\n",
    "            return 0 \n",
    "        count=0\n",
    "        list1=[]\n",
    "        new_nums=nums[:]\n",
    "        while count<len(nums):\n",
    "            new_nums.insert(0,new_nums[-1])\n",
    "            new_nums.pop()\n",
    "            count+=1\n",
    "            if new_nums==sorted(nums):\n",
    "                if count<len(nums):            \n",
    "                    return count\n",
    "        if count==len(nums):\n",
    "            return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        Tnums=nums.copy()\n",
    "        Tnums.sort()\n",
    "        times=0\n",
    "        Len=len(nums)\n",
    "        while nums!=Tnums:\n",
    "            if Len<times:\n",
    "                return -1\n",
    "            times+=1\n",
    "            nums=nums[-1:]+nums[:-1]\n",
    "        return times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        nums2 = nums\n",
    "        count = 0\n",
    "        if nums == sorted(nums):\n",
    "            return 0\n",
    "        while True:\n",
    "            for k in range(0, len(nums2) - 1):\n",
    "                if nums2[k] > nums2[k + 1]:\n",
    "                    break\n",
    "                if k + 2 == len(nums2):\n",
    "                    return count\n",
    "            nums2.insert(0, nums[-1])\n",
    "            nums2.pop(-1)\n",
    "            count += 1\n",
    "            if count == len(nums)+1:\n",
    "                return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = copy.deepcopy(nums)\n",
    "        ans.sort()\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if nums[i + 1] < nums[i]:\n",
    "                return - 1 if nums[i + 1:] + nums[:i + 1] != ans else n - i - 1 \n",
    "        return 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        nums2 = sorted(nums)\n",
    "        s1 = \"#\".join(map(str, nums))\n",
    "        s2 = \"#\".join(map(str, nums2))\n",
    "        print(s2)\n",
    "        if s1 in s2 + \"#\" + s2:\n",
    "            return nums2.index(nums[0])\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "\n",
    "        while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "            i += 1\n",
    "            \n",
    "        j = i + 1\n",
    "\n",
    "        if i + 1 == n:\n",
    "            return 0\n",
    "        else:\n",
    "            i += 1\n",
    "            while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "                i += 1\n",
    "         \n",
    "            if nums[i] > nums[j - 1] or (i and nums[i] > nums[0]):\n",
    "                return -1  \n",
    "            if i < n - 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return n - j\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        if nums == sorted(nums):\n",
    "            return 0\n",
    "        ns,l = nums * 2,len(nums)\n",
    "        for i in range(1,len(ns)):\n",
    "            if ns[i] < ns[i-1]:\n",
    "                if ns[i:i+l] == sorted(nums):\n",
    "                    return l - i\n",
    "                return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        f = 0\n",
    "        while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "            f = 1\n",
    "            i += 1\n",
    "            \n",
    "        j = i + 1\n",
    "        cmp= max(nums[j - 1], nums[0])\n",
    "        if i + 1 == n:\n",
    "            return 0\n",
    "        else:\n",
    "            i += 1\n",
    "            while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "                i += 1\n",
    "         \n",
    "            if nums[i] > cmp or (f and nums[i] > nums[0]):\n",
    "                return -1  \n",
    "            if i < n - 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return n - j\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        ans = -1\n",
    "        ns = sorted(nums+ [] )\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i:] + nums[:i] == ns:\n",
    "                ans = len(nums) - i \n",
    "                break\n",
    "        if ans == len(nums):ans=0\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        minind = nums.index(min(nums))\n",
    "        shift = (len(nums) - minind) % len(nums)\n",
    "        shifted = nums[minind:] + nums[:minind]\n",
    "        avil = True\n",
    "        for i in range(0,len(nums)-1):\n",
    "            if shifted[i+1] < shifted[i]:\n",
    "                avil = False\n",
    "        if avil:\n",
    "            return shift\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        sortnums=sorted(nums)\n",
    "        maxn,maxn_idx,numsl=0,0,0\n",
    "        for i,n in enumerate(nums):\n",
    "            numsl=numsl+1\n",
    "            if n > maxn:\n",
    "                maxn=n\n",
    "                maxn_idx=i\n",
    "        step=numsl-maxn_idx-1\n",
    "        r=[0]*numsl\n",
    "        for i,n in enumerate(nums):\n",
    "            r[(i+step)%numsl]=n\n",
    "        return step if r==sortnums else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = copy.deepcopy(nums)\n",
    "        ans.sort()\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if nums[i + 1] < nums[i]:\n",
    "                return - 1 if nums[i + 1:] + nums[:i + 1] != ans else n - i - 1 \n",
    "        return 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = copy.deepcopy(nums)\n",
    "        ans.sort()\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if nums[i + 1] < nums[i]:\n",
    "                return - 1 if nums[i + 1:] + nums[:i + 1] != ans else n - i - 1 \n",
    "        return 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        f = 0\n",
    "        while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "            f = 1\n",
    "            i += 1\n",
    "            \n",
    "        j = i + 1\n",
    "        cmp= nums[j - 1]\n",
    "\n",
    "        if i + 1 == n:\n",
    "            return 0\n",
    "        else:\n",
    "            i += 1\n",
    "            while i + 1 < n and nums[i + 1] > nums[i]:\n",
    "                i += 1\n",
    "         \n",
    "            if nums[i] > cmp or (f and nums[i] > nums[0]):\n",
    "                return -1  \n",
    "            if i < n - 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return n - j\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        index = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] > nums[index]:\n",
    "                index = i\n",
    "\n",
    "        pre = (index+1)%n\n",
    "        time = n-1\n",
    "        while time>0:\n",
    "            time -= 1\n",
    "            post = (pre+1)%n\n",
    "            if nums[pre]>=nums[post]:\n",
    "                return -1\n",
    "\n",
    "            pre = post\n",
    "\n",
    "        return n-index-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        res = nums.copy()\n",
    "        res.sort()\n",
    "        count = 0\n",
    "        while res != nums:\n",
    "            tmp = nums.pop()\n",
    "            nums.insert(0, tmp)\n",
    "            count += 1\n",
    "\n",
    "            if count > len(nums):\n",
    "                count = -1\n",
    "                break\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        mid = 0\n",
    "        temp = 0\n",
    "        #找两段中点\n",
    "        for i in range(0, len(nums)):\n",
    "            if temp < nums[i]:\n",
    "                temp = nums[i]\n",
    "                mid = i\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        if mid == len(nums)-1:\n",
    "            # 若是一段return 0\n",
    "            return 0\n",
    "        else:\n",
    "            # 若是一段以上，必须是两段。所以：判断第二段是递增，且最后一个值小于第一个值，否则return -1\n",
    "            if nums[0] <= nums[len(nums)-1]:\n",
    "                return -1\n",
    "            t = 0\n",
    "            m = 0\n",
    "            for j in range(mid+1, len(nums)):\n",
    "                if t < nums[j]:\n",
    "                    t = nums[j]\n",
    "                    m = j\n",
    "                else:\n",
    "                    break\n",
    "            if m == len(nums)-1:\n",
    "                return len(nums)-mid-1\n",
    "            else:\n",
    "                return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        last_val = 0\n",
    "        idxs = []\n",
    "        for idx, val in enumerate(nums):\n",
    "            if val < last_val:\n",
    "                idxs.append((idx, val))\n",
    "            last_val = val\n",
    "                \n",
    "        print(idxs)\n",
    "        if len(idxs) > 1: return -1\n",
    "        \n",
    "        if len(idxs) == 0: return 0\n",
    "        \n",
    "        if len(idxs) == 1 and nums[0] < nums[-1]: return -1\n",
    "        \n",
    "        return len(nums) - idxs[0][0] \n",
    "        \n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRightShifts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = copy.deepcopy(nums)\n",
    "        ans.sort()\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if nums[i + 1] < nums[i]:\n",
    "                return - 1 if nums[i + 1:] + nums[:i + 1] != ans else n - i - 1 \n",
    "        return 0\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
